//
// Created by 86138 on 2025/6/20.
//
#include "BSTree.h"
#include <iostream>

using namespace std;

namespace sweetcookie9_2 {

    BSTree SearchBST(BSTree T, KeyType key) {
        if (T == nullptr || key == T->data.key) {
            return T; // 根据返回T节点判断查找结果，为null说明查找失败，否则返回找到的节点。在删除元素的时候，这个是更合理的
        } else if (key < T->data.key) {
            return SearchBST(T->lchild, key);
        } else {
            return SearchBST(T->rchild, key);
        }
    }

    Status SearchBST(BSTree T, KeyType key, BSTree f, BSTree &p) {
        /* 若查找成功，指针p指向该数据元素节点，并返回TRUE；否则p指向查找路径上访问的最后一个节点并返回FALSE，指针f指向T的双亲
         * f的初始调用值始终为NULL
         * */
        if (T == nullptr) {
            p = f;
            return FALSE;
        } else if (key == T->data.key) {
            p = T;
            return TRUE;
        } else if (key < T->data.key) {
            return SearchBST(T->lchild, key, T, p);
        } else {
            return SearchBST(T->rchild, key, T, p);
        }

    }

    Status InsertBST(BSTree &T, ElemType e) {
        BSTree p, s;
        if (!SearchBST(T, e.key, NULL, p)) {
            s = (BSTree) malloc(sizeof(BSTNode));
            s->data = e;
            s->lchild = s->rchild = nullptr;

            if (!p) {
                T = s;
            } else if (e.key < p->data.key) {
                p->lchild = s;
            } else {
                p->rchild = s;
            }
            return TRUE;
        }

        return FALSE;
    }

    void InOrderTraverse(BSTree T) {
        if (T) {
            InOrderTraverse(T->lchild);
            cout << "(" << T->data.key << ", " << T->data.others << ") ";
            InOrderTraverse(T->rchild);
        }
    }

    void PreOrderTraverse(BSTree T) {
        if (T) {
            cout << "(" << T->data.key << ", " << T->data.others << ") ";
            PreOrderTraverse(T->lchild);
            PreOrderTraverse(T->rchild);
        }
    }

    void InputFromFile(FILE* f, ElemType &c) {
        fscanf(f, "%d%d", &c.key, &c.others);
    }

    Status DeleteBST(BSTree &T, KeyType key) {
        if (!T) return FALSE;

        if (key == T->data.key) {
            DeleteBST(T);
            return TRUE;
        } else if (key < T->data.key) {
            return DeleteBST(T->lchild, key);
        } else {
            return DeleteBST(T->rchild, key);
        }
    }

    void DeleteBST(BSTree &p) {
        BSTree s, q;
        q = p;
        if (!p->lchild) { // 删除叶子节点也会在此被处理掉
            p = p->rchild;
            free(q);
        } else if (!p->rchild) {
            p = p->lchild;
            free(q);
        } else {
            s = p->lchild;
            while (s->rchild) {
                q = s;
                s = s->rchild;
            }
            p->data = s->data;
            if (q != p) {
                q->rchild = s->lchild;
            } else {
                q->lchild = s->lchild;
            }
            free(s);
        }
    }
}

//using namespace sweetcookie9_2;
//
//int main() {
//    system("chcp 65001");
//
//    sweetcookie9_2::ElemType r;
//    Status k;
//    int n;
//    KeyType j;
//    BSTree T, p;
//    T = nullptr;
//    FILE *f;
//    f = fopen("D:\\playground5\\qingdao-university\\09-search\\f8-4.txt", "r");
//    fscanf(f, "%d", &n);
//    for (int i = 0; i < n; i++) {
//        InputFromFile(f, r);
//        k = InsertBST(T, r);
//        if (!k) {
//            printf("二叉排序树dt中已存在关键字为%d的数据，故 (%d,%d) 无法插入到dt中。\n",
//                   r.key, r.key, r.others);
//        }
//    }
//    fclose(f);
//    printf("中序遍历二叉排序树：\n");
//    InOrderTraverse(T);
//    printf("\n先序遍历二叉排序树：\n");
//    PreOrderTraverse(T);
//
//    j = 70;
//    printf("\n搜索值为%d的节点\n", j);
//
//    p = SearchBST(T, j);
//    if (p) {
//        printf("找到了节点%d，删除该节点\n", j);
//        DeleteBST(T, j);
//        printf("中序遍历二叉排序树：\n");
//        InOrderTraverse(T);
//        printf("\n先序遍历二叉排序树：\n");
//        PreOrderTraverse(T);
//    } else {
//        printf("没有找到节点%d\n", j);
//    }
//
//    return 0;
//}